#ifndef __BINARYSEARCH_H__
#define __BINARYSEARCH_H__

#include <vector>
using namespace std;

/*
* leetcode 704 二分查找
* 在一个有序数组中, 查找元素等于 target 的元素的索引
*/
/*
* 这里需要注意搜索边界的问题
* 常用的区间有 : [], [)
*/
int BinarySearchI(const vector<int>& nums, int target) {
	//使用左闭右开 [), right = nums.size()
	int left = 0, right = nums.size();

	//左闭右开, left != right
	while (left < right) {
		int mid = left + (right - left) / 2;

		if (nums[mid] == target)
			return mid;

		if (nums[mid] < target)
			left = mid + 1;

		else  //由于 [) , 虽然判断过 mid, 但是不能赋值为 mid - 1
			right = mid;
	}

	return -1;
}

// [] 左闭右闭
int BinarySearchII(const vector<int>& nums, int target) {
	//使用左闭右开 [], right = nums.size() - 1
	int left = 0, right = nums.size() - 1;
	
	//左闭右闭, left == right 
	while (left <= right) {
		int mid = left + (right - left) / 2;

		if (nums[mid] == target)
			return mid;

		if (nums[mid] < target)
			left = mid + 1;

		else  //由于 [], 并且已经判断过 mid, 所以为 mid - 1
			right = mid - 1;
	}

	return -1;
}

#endif // !__BINARYSEARCH_H__
